/*
*
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000

  - @author ala
  - @date 2024-10-09 10:28
*/
package main

import (
	"fmt"
	"sort"
)

func main() {
	//rewardValues := []int{1, 1, 3, 3}
	rewardValues := []int{1, 6, 4, 3, 2}

	fmt.Println(maxTotalReward(rewardValues))
}

func maxTotalReward(rewardValues []int) int {
	return V1(rewardValues)
}

/**
 *	1）dp[i][j]表示前i个数能否凑出j
 *		dp[0][0] = true
 *		dp[i][j] = dp[i - 1][j] || dp[i - 1][j - v]
 *		其中：v = rewardValues[i - 1]
 *			 j - v >= 0
 *			 v > j - v
 *	2）i ∈ [0, N - 1]
 *	   j ∈ [0, 2 * max(rewardValues) - 1]
 */
func V1(rvs []int) int {
	N := len(rvs)
	mx := 0
	//	去重，排序
	set, nums := map[int]struct{}{}, make([]int, 0, N)
	for _, n := range rvs {
		if _, ex := set[n]; !ex {
			set[n] = struct{}{}
			nums = append(nums, n)
			mx = max(mx, n)
		}
	}
	N = len(nums)
	//	如果存在mx - 1，则2mx - 1为最大值
	set = make(map[int]struct{}, N)
	set[0] = struct{}{}
	for _, n := range nums {
		if _, ex := set[mx-1-n]; ex {
			return mx<<1 - 1
		}
		set[n] = struct{}{}
	}

	sort.Ints(nums)
	//sort.Slice(nums, func(i, j int) bool {
	//	return i < j
	//})
	N, mx = len(nums), nums[len(nums)-1]
	dp := make([][]bool, N+1)
	for i := range dp {
		dp[i] = make([]bool, mx<<1)
	}
	dp[0][0] = true
	for i := 1; i <= N; i++ {
		v := nums[i-1]
		for j := 0; j < mx<<1 && j < v<<1; j++ {
			dp[i][j] = dp[i-1][j]
			if j >= v {
				dp[i][j] = dp[i][j] || dp[i-1][j-v]
			}
		}
	}
	for j := mx<<1 - 1; j >= 0; j-- {
		if dp[N][j] {
			return j
		}
	}
	return 0
}
